/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: syyyy
 * Date: 2025-10-25
 * Time: 10:35
 */
import java.util.Scanner;

public class KaratsubaMultiplication {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入第一个大整数: ");
        String x = scanner.nextLine();
        System.out.print("请输入第二个大整数: ");
        String y = scanner.nextLine();
        scanner.close();

        String result = karatsubaMultiply(x, y);
        System.out.println("乘积结果: " + result);
    }

    /**
     * Karatsuba算法实现大整数乘法
     * @param x 第一个大整数（字符串形式）
     * @param y 第二个大整数（字符串形式）
     * @return 乘积结果（字符串形式）
     */
    public static String karatsubaMultiply(String x, String y) {
        // 步骤1：处理输入（移除可能的前导零，确保输入合法）
        x = removeLeadingZeros(x);
        y = removeLeadingZeros(y);

        // 处理特殊情况：有一个数为0
        if (x.equals("0") || y.equals("0")) {
            return "0";
        }

        // 步骤2：获取字符串长度，取两者中的最大值
        int lenX = x.length();
        int lenY = y.length();
        int n = Math.max(lenX, lenY);

        // 步骤3：确保n是2的幂，不足则填充前导零
        n = nextPowerOfTwo(n);
        x = padWithLeadingZeros(x, n);
        y = padWithLeadingZeros(y, n);

        // 递归终止条件：当n=1时直接相乘
        if (n == 1) {
            int product = (x.charAt(0) - '0') * (y.charAt(0) - '0');
            return String.valueOf(product);
        }

        // 步骤4：计算分割点（n/2）
        int half = n / 2;

        // 步骤5：分割成高低部分
        String xHigh = x.substring(0, half);      // x的高位部分
        String xLow = x.substring(half);          // x的低位部分
        String yHigh = y.substring(0, half);      // y的高位部分
        String yLow = y.substring(half);          // y的低位部分

        // 步骤6：递归计算三个关键乘积
        String z0 = karatsubaMultiply(xLow, yLow);                  // z0 = xLow * yLow
        String z2 = karatsubaMultiply(xHigh, yHigh);                // z2 = xHigh * yHigh
        String sumX = add(xHigh, xLow);                             // xHigh + xLow
        String sumY = add(yHigh, yLow);                             // yHigh + yLow
        String z1 = karatsubaMultiply(sumX, sumY);                  // (xHigh+xLow)*(yHigh+yLow)
        z1 = subtract(subtract(z1, z2), z0);                        // z1 = z1 - z2 - z0

        // 合并结果：z2*10^(2*half) + z1*10^half + z0
        String part1 = z2 + "0".repeat(2 * half);  // z2 * 10^(2*half)
        String part2 = z1 + "0".repeat(half);      // z1 * 10^half
        String result = add(add(part1, part2), z0);

        // 步骤7：输出最终结果（移除可能的前导零）
        return removeLeadingZeros(result);
    }

    /**
     * 计算大于等于n的最小2的幂
     */
    private static int nextPowerOfTwo(int n) {
        if (n <= 0) return 1;
        int power = 1;
        while (power < n) {
            power <<= 1;  // 等价于power *= 2
        }
        return power;
    }

    /**
     * 给字符串填充前导零，使其长度为targetLen
     */
    private static String padWithLeadingZeros(String s, int targetLen) {
        if (s.length() >= targetLen) {
            return s;
        }
        StringBuilder sb = new StringBuilder();
        int zerosToAdd = targetLen - s.length();
        for (int i = 0; i < zerosToAdd; i++) {
            sb.append('0');
        }
        sb.append(s);
        return sb.toString();
    }

    /**
     * 移除字符串的前导零
     */
    private static String removeLeadingZeros(String s) {
        if (s.length() == 1) return s;  // 单个字符（包括"0"）直接返回
        int firstNonZero = 0;
        while (firstNonZero < s.length() && s.charAt(firstNonZero) == '0') {
            firstNonZero++;
        }
        // 如果全是零，返回"0"
        return firstNonZero == s.length() ? "0" : s.substring(firstNonZero);
    }

    /**
     * 大整数加法（辅助函数）
     */
    private static String add(String a, String b) {
        a = removeLeadingZeros(a);
        b = removeLeadingZeros(b);

        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0 || carry > 0) {
            int digitA = (i >= 0) ? (a.charAt(i--) - '0') : 0;
            int digitB = (j >= 0) ? (b.charAt(j--) - '0') : 0;
            int sum = digitA + digitB + carry;
            carry = sum / 10;
            sb.append(sum % 10);
        }

        return sb.reverse().toString();
    }

    /**
     * 大整数减法（辅助函数，确保a >= b）
     */
    private static String subtract(String a, String b) {
        a = removeLeadingZeros(a);
        b = removeLeadingZeros(b);

        // 确保a >= b，如果a < b则交换并记录负号（本问题中不会出现此情况）
        if (compare(a, b) < 0) {
            String temp = a;
            a = b;
            b = temp;
        }

        int i = a.length() - 1;
        int j = b.length() - 1;
        int borrow = 0;
        StringBuilder sb = new StringBuilder();

        while (i >= 0 || j >= 0) {
            int digitA = (i >= 0) ? (a.charAt(i--) - '0') : 0;
            int digitB = (j >= 0) ? (b.charAt(j--) - '0') : 0;

            digitA -= borrow;
            borrow = 0;

            if (digitA < digitB) {
                digitA += 10;
                borrow = 1;
            }

            sb.append(digitA - digitB);
        }

        return removeLeadingZeros(sb.reverse().toString());
    }

    private static int compare(String a, String b) {
        a = removeLeadingZeros(a);
        b = removeLeadingZeros(b);

        if (a.length() != b.length()) {
            return Integer.compare(a.length(), b.length());
        }
        for (int i = 0; i < a.length(); i++) {
            int digitA = a.charAt(i) - '0';
            int digitB = b.charAt(i) - '0';
            if (digitA != digitB) {
                return Integer.compare(digitA, digitB);
            }
        }
        return 0;
    }
}